from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """
    使用广度优先搜索，一层一层遍历即可
    """

    @staticmethod
    def bfs(root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        # 创建队列
        queue, result = [root], []
        # 开始遍历每一层
        while queue:
            # 将每一层的结点的值放进结果的队列中
            result.append([node.val for node in queue])
            # 遍历每一层每一个结点的下一层
            children = []
            for node in queue:
                # 有左子树，将左子树入队
                if node.left:
                    children.append(node.left)
                # 将右子树入队
                if node.right:
                    children.append(node.right)
            # 将下一层的遍历队列放到queue中继续遍历
            queue = children
        # 遍历结束，返回结果
        return result


class DFS:
    """
    深度优先搜索：输出的每一层的数都是从左到右，所以要先对左子树进行递归，再对右子树进行递归
    注意点：每访问到一个子树，需要将其放入对应的层级的列表中，所以当该层级第一次被遍历到时，需要
           初始化一个该层的队列， len(result) == level(level从0开始，result长度等于
           level时表明进入到了新的层级)
           也可以用一个hash表存储当前层级的列表 {0: [1,2], 1: [3,4,5,6]}
    """

    def solution(self, root: TreeNode) -> List[List[int]]:
        result = []
        self.helper(root, 0, result)
        return result

    def helper(self, root: TreeNode, level: int, result: list):
        # terminator
        if not root:
            return []
        # 遍历到新的层级时，初始化一个空列表, process
        if len(result) == level:
            result.append([])
        # 将该节点值放入该层级的列表中result[level]
        result[level].append(root.val)
        # 递归每一层左子树  drill down
        if root.left:
            self.helper(root.left, level + 1, result)
        # 递归每一层右子树
        if root.right:
            self.helper(root.right, level + 1, result)
